package com.aurora.leetcode.answer.dynamic_plan;

/**
 * @author : qiaodan
 * @date : 2025/4/22 21:21
 * @description 5.最长回文子串
 *给你一个字符串s，找到
 * 中最长的回文 子串。
 * 示例 1:
 * 输入：8- "babad"
 * 输出： "bab"
 * 解释："aba"同样是符合题意的答案。
 * 示例 2：
 * 输入：8- "cbbd"
 * 输出："bb"
 * 提示：
 * s. length <= 1008
 * 仅由数字和英文字母组成
 */
public class LongestPalindrome_5 {
    // 我的解决方案-双指针
    public String longestPalindrome(String s) {
        String result = "";
        if (s.length() == 0) return s;
        int left = 0;
        int right = 0;
        for (; left < s.length(); ) {
            int m = left, n = right;
            for (; m <= n; ) {
                if (s.charAt(m) == s.charAt(n)) {
                    ++m;
                    --n;
                }else{
                    break;
                }
            }
            if (m > n) {
                if (result.length() < (right - left) + 1)
                    result = s.substring(left, right + 1);
            }
            if (right < s.length() - 1) {
                right++;
            } else {
                right = ++left;
            }
        }
        return result;
    }

    // 参考实现-动态规划
    public String longestPalindrome2(String s) {
        // 参考实现（动态规划）
        int len = s.length();
        if(len < 2) return s;
        int begin = 0;
        int maxLen = 1;
        // mark[i][j] 标记从i->j是否为回文串
        boolean[][] mark = new boolean[len][len];
        for(int i=0; i<s.length(); ++i){
            mark[i][i] = true;
        }
        char[] chars = s.toCharArray();
        for(int l = 2; l<=len; ++l){
            for(int m=0; m<=len-l; ++m){
                int n = m+l-1;
                if(chars[m] != chars[n]){
                    mark[m][n] = false;
                }else{
                    if(l == 2){
                        mark[m][n] = true;
                    }else{
                        mark[m][n] = mark[m+1][n-1];
                    }
                }
                if(mark[m][n] && l>maxLen){
                    maxLen = l;
                    begin = m;
                }
            }
        }
        return s.substring(begin, begin+maxLen);
    }
    // 参考实现Manacher算法
    public String longestPalindrome3(String s) {
        return null;
    }

    public static void main(String[] args) {
        String s = "babad";
//        String s = "cbbd";
        LongestPalindrome_5 sol = new LongestPalindrome_5();
        System.out.println(sol.longestPalindrome2(s));

    }


}
